﻿#define _CRT_SECURE_NO_WARNINGS 1
#include<iostream>
#include<map>
#include<vector>
#include<algorithm>
using namespace std;
//解题思路：
//该题最主要的的难点在于题目要求“出现次数相同的单词按照字典序排列”
//我们可以使用map来计算每个单词出现的次数，并将这些单词按照字典序排序
//但还需要找到前k个出现频率最高的单词，此时就需要按照map中单词出现的次数进行排序了
//同时还需要注意，在次数相同时不能破坏map中单词的字典序，也就是说，此时需要一个稳定排序
//而map自动排序为不稳定，sort虽然快但也不稳定，最终选择了stable_sort（稳定快排函数）
//同时，由于sort与stable_sort均需要随机迭代器，且vector调用快排效率最高
//所以最终选用了vector来接手map中的数据并进行稳定排序，排序结束后，
//将vector容器中的前k个元素放入新的vector<string>返回即可

class Solution {
public:
    class Compare
    {
    public:
        bool operator()(pair<string, int> s1, pair<string, int> s2)
        {
            return s1.second > s2.second;//使用pair的second进行比较，也就是根据单词出现的次数进行比较，s1大时为真，出现次数多的排在前面
        }
    };
    vector<string> topKFrequent(vector<string>& words, int k) {
        map<string, int> m;
        //使用map统计每个单词出现的次数，且此时map中排序为按照字典顺序升序排列
        for (const auto& e : words)
        {
            ++m[e];
        }
        //使用vector接收map中的元素（为后续排序做准备-》已知sort排序需要随机迭代器，且随机迭代器容器中vector调用sort速度最快）
        vector<pair<string, int>> v(m.begin(), m.end());
        //使用排序函数对vector中单词出现的次数进行排序（注：为避免排序时造成“相同次数的单词的字典序混乱”这里要使用稳定排序（如stable_sort））
        stable_sort(v.begin(), v.end(), Compare());//尽管pair类型具备比较运算符重载，但不符合此时需要的逻辑，故需要创建仿函数做stable_sort的第三个参数
        //将符合条件的前k个单词存入vector做返回值
        vector<string> rv;
        for (size_t i = 0; i < k; ++i)
        {
            rv.push_back(v[i].first);
        }
        return rv;
    }
};

//补充，在思路中表达了“需要使用稳定排序”，这也是第一次认识到稳定排序的实际作用
//同时，其实可以使用不稳定排序+自定义仿函数实现“伪稳定排序”，
//且这种方式的效率有可能高于使用stable_sort函数
//举例来说，可以创建以下仿函数作为sort的比较函数：
class Compare
{
public:
    bool operator()(pair<string, int> s1, pair<string, int> s2)
    {
        return s1.second > s2.second || (s1.second == s2.second && s1.first < s2.first);
    }
};
//上面为sort函数设计的仿函数中，由于：
//sort乃至大多数排序中，仿函数结果为真则​​表示第一个参数应排在第二个参数之前
//所以只需添加||(s1.second == s2.second && s1.first < s2.first)便可以实现伪稳定排序
//注：之所以仍需要“&& s1.first < s2.first”，是因为sort排序到底是不稳定排序，尽管map已经进行了字典序
//排序，但在sort为前面的元素排序过程中，是可能会破坏后面元素的字典序的，因此，还需要&&对是否字典序进行确认
//
//但需注意：堆排是特例，其逻辑恰好相反，为真表示第一个参数应在第二参数后
//使用堆排的自定义仿函数
class CompareP
{
public:
    bool operator()(pair<string, int> s1, pair<string, int> s2)
    {
        return !(s1.second > s2.second || (s1.second == s2.second && s1.first < s2.first));//由于须于其他排序仿函数逻辑相反，所以直接整体取反即可
    }
};
